#include "main/utils.h"
#include "lib/list.h"
using namespace std;

class LRU {
  public:
    LRU(int capacity): capacity(capacity) {};

    int get(int key) {
      if (map.find(key) == map.end()) {
        cout << "can't get " << key << endl;
        return -1;
      }
      DoubleListNode* cur_node = map[key];
      moveToTail(cur_node);
      return cur_node->value;
    }

    void put(int key, int value) {
      if (map.find(key) != map.end()) {
        auto node = map[key];
        node->value = value;
        moveToTail(node);
        return;
      }
      if (map.size() == capacity) {
        auto head_tmp = head;
        head = head->next;
        head->pre = nullptr;
        delete head_tmp;
        map.erase(key);
      }
      DoubleListNode* new_node = new DoubleListNode();
      new_node->value = value;
      if (!head && !tail) {
        head = new_node;
        tail = new_node;
      } else {
        tail->next = new_node;
        new_node->pre = tail;
        tail = new_node;
      }
      map[key] = new_node;
    }

  public:
    DoubleListNode* head = nullptr;
    DoubleListNode* tail = nullptr;
    map<int, DoubleListNode*> map;
    int capacity;

  private:
    void moveToTail(DoubleListNode* node) {
      if (node == tail)
        return;
      if (node == head) {
        head = node->next;
        head->pre = nullptr;
      } else {
        node->pre->next = node->next;
        node->next->pre = node->pre;
      }
      tail->next = node;
      node->pre = tail;
      tail = node;
      tail->next = nullptr;
    }
};

int main() {
  LRU lru(5);
  lru.put(1, 2);
  cout << "put (1, 2): " << endl;
  PrintDoubleList(lru.head);

  lru.put(3, 4);
  cout << "put (3, 4): " << endl;
  PrintDoubleList(lru.head);

  lru.put(5, 6);
  cout << "put (5, 6): " << endl;
  PrintDoubleList(lru.head);

  lru.put(7, 8);
  cout << "put (7, 8): " << endl;
  PrintDoubleList(lru.head);

  lru.put(9, 10);
  cout << "put (9, 10): " << endl;
  PrintDoubleList(lru.head);

  lru.put(11, 12);
  cout << "put (11, 12): " << endl;
  PrintDoubleList(lru.head);

  auto ret = lru.get(3);
  cout << "get 3: " << ret << endl;
  PrintDoubleList(lru.head);

  lru.put(11, 5);
  cout << "put (11, 5): " << endl;
  PrintDoubleList(lru.head);

  return 0;
}
